package com.zdb.algorithm.floyd;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class FloydAlgorithm {

    public static void main(String[] args) {
        Graph graph = createGraph();
        graph.print();
        System.err.println("--------- floyd ---------");
        graph.floyd();
        graph.print();
    }


    public static Graph createGraph() {
        char[] vertexs = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        Graph graph = new Graph(vertexs);

        // 增加边
        graph.addEdge('A', 'C', 7);
        graph.addEdge('A', 'B', 5);
        graph.addEdge('A', 'G', 2);
        graph.addEdge('B', 'G', 3);
        graph.addEdge('B', 'D', 9);
        graph.addEdge('C', 'E', 8);
        graph.addEdge('E', 'G', 4);
        graph.addEdge('E', 'F', 5);
        graph.addEdge('F', 'G', 6);
        graph.addEdge('F', 'D', 4);

        return graph;
    }
}


class Graph {
    /**
     顶点
     */
    char[] vertexs;
    /**
     * 存放边及权重
     */
    int[][] weight;

    /**
     * 存放顶点的前驱节点
     */
    int[][] pre;

    /**
     顶点与vertexs中下标的对应关系
     */
    Map<Character, Integer> vertex2index;



    public static final int INF = Integer.MAX_VALUE / 5;

    public Graph(char[] vertexs) {
        this.vertexs = vertexs;
        vertex2index = new HashMap<>();
        for (int i = 0; i < vertexs.length; i++) {
            vertex2index.put(vertexs[i], i);
        }
        weight = new int[vertexs.length][vertexs.length];
        pre = new int[vertexs.length][vertexs.length];;

        for (int i = 0; i < vertexs.length; i++) {
            Arrays.fill(weight[i], INF);
            Arrays.fill(pre[i], i);
            weight[i][i] = 0;
        }
    }

    public void floyd() {
        // 保存距离的中间变量
        int len = 0;

        // 中间节点K vertexs[]
        for (int k = 0; k < vertexs.length; k++) {
            // 出发节点i vertexs[]
            for (int i = 0; i < vertexs.length; i++) {
                // 终点j vertexs[]
                for (int j = 0; j < vertexs.length; j++) {
                    String info = String.format("%s-(%d)-%s-(%d)-%s\n",
                            getVertexByIndex(i), weight[i][k],
                            getVertexByIndex(k), weight[k][j],
                            getVertexByIndex(j));
//                    System.out.println(info);
                    len = weight[i][k] + weight[k][j];
                    if(len < weight[i][j]) {
                        weight[i][j] = len;
                        pre[i][j] = pre[k][j];
                        // 个人以为是k
//                        pre[i][j] = k;
                    }
                }
            }
        }
    }

    public int getVertexSize() {
        return vertexs.length;
    }

    /**
     * 增加边
     * @param a
     * @param b
     * @param weight
     */
    public void addEdge(char a, char b, int weight) {
        int aIdx = vertex2index.get(a);
        int bIdx = vertex2index.get(b);
        if(this.weight[aIdx][bIdx] == INF && weight != INF) {
            this.weight[aIdx][bIdx] = weight;
            this.weight[bIdx][aIdx] = weight;
        }
    }

    /**
     * 获取顶点的下标
     * @param v
     * @return
     */
    public int getVertexIndex(char v) {
        return vertex2index.get(v);
    }

    /**
     * 通过下标获取顶点
     * @param index
     * @return
     */
    public char getVertexByIndex(int index) {
        return vertexs[index];
    }

    public void print() {
        // 打印邻接矩阵和前驱节点状况
        for (int j = 0; j < vertexs.length; j++) {
            int[] link = weight[j];
            int[] p = pre[j];
            System.out.print("[");
            for (int i = 0; i < link.length; i++) {
                if(link[i]==INF) {
                    System.out.printf(" %5s", "INF");
                } else {
                    System.out.printf(" %5d", link[i]);
                }
                if(i != link.length -1) {
                    System.out.print(",");
                }
            }
            System.out.println("]");

            System.out.print("(");
            for (int i = 0; i < p.length; i++) {
                System.out.printf(" %s-%s[%s]", getVertexByIndex(j), getVertexByIndex(i), getVertexByIndex(p[i]));
            }
            System.out.println(")");
        }
    }
}
